1. Field of the Invention
This invention relates to a method and apparatus for transforming an attributed tree valid under an attribute grammar to another attributed tree valid under another attribute grammar.
2. Background of the Invention
Some of the expected (but only partially realized) benefits of electronic documents over paper documents include enhanced document processing capabilities and easier manipulation of documents, such as creation, editing, updating, storage, access, and delivery of documents. A key enabler for such enhancement in known systems is their ability to represent not only the contents of documents but also various meta-information about the contents. For instance, document structures such as chapter, section, and paragraph breaks can be explicitly represented for enhanced browsing, retrieval, and component reuse.
However, one central technical problem involves how to represent such meta-information in a way computers and humans can easily manipulate. One prominent approach to this problem is to adapt formal grammars (used to describe programming languages) to represent hierarchical structures of documents (e.g., chapter, section, and paragraph breaks). The Standard Generalized Markup Languages (SGML), for instance, uses an extension of context-free grammars for this purpose.
This invention addresses two insufficiencies in the existing grammar-based approaches to representing and manipulating electronic documents. First, these approaches have only a limited capability to specifying attributes and their dependencies. For example, an attribute of "section" may depend on certain attributes of "chapter". Second, these approaches have an inadequate ability to specify and compute document transformation. That is, they are unable to fully transform document instances as derivation trees of one grammar to document instances as derivation trees of another grammar.
The first limitation leads to the second. The idea of document transformation is important for a variety of reasons. For example, while the notion of grammar-based document schema is useful in capturing structural information of documents, it also imposes some rigidity on kinds of documents one can create under a given schema. Because one often wishes to modify the given schema in order to accommodate features of document design not originally considered, this creates the need to transform documents from the given schema to the modified schema. Additionally, some institution documents are so large and complex that it is highly desirable to be able to specify and compute more customized and manageable views as a document transformation. Furthermore, it is often possible and desirable to automatically assemble documents from existing documents as a document transformation. For example, generating a draft of a technical report of a research laboratory from previously submitted project reports.